package leetcode.array;

/*
 845. 数组中的最长山脉

 我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：
 B.length >= 3
 存在 0 < i?< B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
 （注意：B 可以是 A 的任意子数组，包括整个数组 A。）

 给出一个整数数组 A，返回最长 “山脉”?的长度。
 如果不含有 “山脉”?则返回 0。

 示例 1：
 输入：[2,1,4,7,3,2,5]
 输出：5
 解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。

 示例 2：
 输入：[2,2,2]
 输出：0
*/

import java.util.Arrays;

public class LongestMountain845 {
    public static void main(String[] args) {
        int[] nums;

//        nums = new int[]{2,1,4,7,3,2,5};
//        System.out.println(Arrays.toString(nums));
//        System.out.println(test(nums));
//
//        nums = new int[]{2,2,2};
//        System.out.println(Arrays.toString(nums));
//        System.out.println(test(nums));
//
//        nums = new int[]{0,1,2,3,4,5,4,3,2,1,0};
//        System.out.println(Arrays.toString(nums));
//        System.out.println(test(nums));

        nums = new int[]{875,884,239,731,723,685};
        System.out.println(Arrays.toString(nums));
        System.out.println(test(nums));
    }

    private static int test(int[] A) {
        if(A.length < 3)
            return 0;

        int leftCount;
        int rightCount = 0;
        int maxLength = 0;

        int t = 0;
        for(int i=1; i < A.length - 1; i++) {

            // 寻找左侧山元素数
            leftCount = 0;
            for (int l = i; l > 0; l--) {

                t = l - 1;
                if (A[t] >= A[l]) {
                    break;
                } else {
                    leftCount++;
                }
            }

            // 寻找右侧山元素数
            rightCount = 0;
            for (int r = i; r < A.length - 1; r++) {
                t = r + 1;
                if (A[r] <= A[t]) {
                    break;
                } else {
                    rightCount++;
                }
            }

            // 处理左侧山和右侧山的元素计数情况
            if (leftCount != 0 && rightCount != 0) {   // 左侧山和右侧山都有元素，则山脉成立
                maxLength = (rightCount + leftCount + 1) > maxLength ? rightCount + leftCount + 1 : maxLength;
                i = i + rightCount;
                continue;
            } else {    // 山脉不成立
                if (rightCount == 0) // 右侧山没有元素，直接以下一个元素作为山顶再次迭代
                    continue;
                else    // 直接将现在的山顶右移到右侧山的下一个元素，再次迭代
                    i = i + rightCount;
            }
        }

        return maxLength;
    }
}
